package algorithm.easy;

import link.MyLinkedList;

import java.util.HashMap;
import java.util.Map;

public class Solution70 {
    private static Map<Integer,Integer> map = new HashMap<>();
    //输入：n = 3
    //输出：3
    //解释：有三种方法可以爬到楼顶。
    //1. 1 阶 + 1 阶 + 1 阶
    //2. 1 阶 + 2 阶
    //3. 2 阶 + 1 阶
    public static int climbStairs(int n) {
        Integer cacheValue = map.get(n);
        if(cacheValue!=null){
            return cacheValue;
        }
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }
        int value =  climbStairs(n-1) +climbStairs(n-2);
        map.put(n,value);
        return value;
    }

    public static void main(String[] args){
        int n =45;
        System.out.println(climbStairs(n));
    }
}
